import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// https://leetcode.cn/problems/combination-sum-iii
public class CombinationSum3 {

    class Solution {

        private  List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combinationSum3(int k, int n) {
            backtracking(new ArrayList<>(),n, 1,k );
            return res;


        }

        private void backtracking(List<Integer> path , int sum , int start, int k )
        {

            if(path.size() == k && sum == 0)
            {
                res.add(new ArrayList<>(path));
                return ;
            }
            if(path.size() >= k) return ;

            for(int i = start; i <= 9 && i <= sum ; i ++)
            {
                path.add(i);
                backtracking(path,sum-i,i+1,k);
                path.remove(path.size()-1);
            }

        }
    }
}
